When making decisions under uncertainty, the optimal choices are often difficult to discern, especially if not enough information has been gathered. Two key questions in this regard relate to whether one should stop the information gathering process and commit to a decision (stopping criterion), and if not, what information to gather next (selection criterion). In this paper, we show that the recently introduced notion, Same-Decision Probability (SDP), can be useful as both a stopping and a selection criterion, as it can provide additional insight and allow for robust decision making in a variety of scenarios. This query has been shown to be highly intractable, being PP^PP-complete, and is exemplary of a class of queries which correspond to the computation of certain expectations. We propose the first exact algorithm for computing the SDP, and demonstrate its effectiveness on several real and synthetic networks. Finally, we present new complexity results, such as the complexity of computing the SDP on models with a Naive Bayes structure. Additionally, we prove that computing the non-myopic value of information is complete for the same complexity class as computing the SDP.

When using graphical models for decision making, the presence of unobserved variables  may hinder our ability to reach the correct decision.  A fundamental question here is whether or not  one is ready to make a decision (stopping criteria), and if not, what additional  observations should be made in order to better prepare for a decision  (selection criteria).  A recently introduced notion, the Same-Decision Probability (SDP), has been shown to be useful  as both a stopping and a selection criteria.  This query has been shown to be highly intractable,  being PP^PP-complete, and is exemplary of a class of queries which correspond to the computation of certain expectations.  We propose the first exact algorithm for computing the SDP in this paper, and demonstrate its effectiveness on several real and synthetic networks.  We also present a new complexity result for computing the SDP on models with a Naive Bayes structure.